lib/Mi manual de algoritmos/version_actual/src/geometria/check_segment_intersection.cpp

   1 /*
   2   Returns the cross product of the segment that goes from
   3   (x1, y1) to (x3, y3) with the segment that goes from
   4   (x1, y1) to (x2, y2)
   5 */
   6 int direction(int x1, int y1, int x2, int y2, int x3, int y3) {
   7     return (x3 - x1) * (y2 - y1) - (y3 - y1) * (x2 - x1);
   8 }
   9
  10 /*
  11   Finds the intersection between two segments (Not infinite
  12   lines!)
  13   Segment 1 goes from point (x0, y0) to (x1, y1).
  14   Segment 2 goes from point (x2, y2) to (x3, y3).
  15
  16   (Can be modified to find the intersection between a segment
  17   and a line)
  18
  19   Handles the case when the 2 segments are:
  20   *Parallel but don't lie on the same line (No intersection)
  21   *Parallel and both lie on the same line (Infinite
  22   *intersections or no intersections)
  23   *Not parallel (One intersection or no intersections)
  24
  25   Returns true if the segments do intersect in any case.
  26 */
  27 bool segment_segment_intersection(int x1, int y1,
  28                                   int x2, int y2,
  29
  30                                   int x3, int y3,
  31                                   int x4, int y4){
  32
  33     int d1 = direction(x3, y3,   x4, y4,   x1, y1);
  34     int d2 = direction(x3, y3,   x4, y4,   x2, y2);
  35     int d3 = direction(x1, y1,   x2, y2,   x3, y3);
  36     int d4 = direction(x1, y1,   x2, y2,   x4, y4);
  37     bool b1 = d1 > 0 and d2 < 0 or d1 < 0 and d2 > 0;
  38     bool b2 = d3 > 0 and d4 < 0 or d3 < 0 and d4 > 0;
  39     if (b1 and b2) return true;
  40     if (d1 == 0 and point_in_box(x1, y1,     x3, y3, x4, y4))
  41         return true;
  42
  43     if (d2 == 0 and point_in_box(x2, y2,     x3, y3, x4, y4))
  44         return true;
  45
  46     if (d3 == 0 and point_in_box(x3, y3,     x1, y1, x2, y2))
  47         return true;
  48
  49     if (d4 == 0 and point_in_box(x4, y4,     x1, y1, x2, y2))
  50         return true;
  51
  52     return false;
  53 }